package com.example.programmerinterview;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.11. 硬币   典型背包问题
 * 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
 * <p>
 * 示例1:
 * <p>
 * 输入: n = 5
 * 输出：2
 * 解释: 有两种方式可以凑成总金额:
 * 5=5
 * 5=1+1+1+1+1
 * 示例2:
 * <p>
 * 输入: n = 10
 * 输出：4
 * 解释: 有四种方式可以凑成总金额:
 * 10=10
 * 10=5+5
 * 10=5+1+1+1+1+1
 * 10=1+1+1+1+1+1+1+1+1+1
 */
public class WaysToChange {
    static final int MOD = 1000000007;
    static int[] coins = {25, 10, 5, 1};

    public static int waysToChange(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int coin : coins) {
            //如果金币不在范围内就不参与循环，等于说每个能循环的金币都要循环一轮，最后将d[j]叠加起来
            for (int j = coin; j <= n; ++j) {
                dp[j] = (dp[j] + dp[j - coin]) % MOD;
            }
        }
        return dp[n];
    }

    /**
     * 518. 零钱兑换 II   与1的区别是直接给了coins数组
     * 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
     * <p>
     * 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
     * <p>
     * 假设每一种面额的硬币有无限个。
     * <p>
     * 题目数据保证结果符合 32 位带符号整数。
     * 示例 1：
     * <p>
     * 输入：amount = 5, coins = [1, 2, 5]
     * 输出：4
     * 解释：有四种方式可以凑成总金额：
     * 5=5
     * 5=2+2+1
     * 5=2+1+1+1
     * 5=1+1+1+1+1
     */
    public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int j = coin; j <= amount; ++j) {
                dp[j] = (dp[j] + dp[j - coin]);
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        System.out.println(WaysToChange.waysToChange(7));
    }
}

class Solution {
    List<String> res = new ArrayList<>();


    public String[] permutation(String S) {
        if (S.length() <= 1) return new String[]{S};

        back(new StringBuilder(), 0, S);
        String[] s = new String[res.size()];
        return res.toArray(s);
    }

    public void back(StringBuilder str, int start, String S) {
        if (str.length() == S.length()) {
            res.add(new String(str));
            return;
        }
        for (int i = start; i < S.length(); i++) {
            str.append(S.substring(i, i + 1));
            back(str, i + 1, S);
            str.deleteCharAt(i);
        }
    }
}